﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    //题目解析，给一个n，表示字符的个数，以及某个字符出现的次数
    //将字符进行哈夫曼编码，即将二进制去表示某一个字符，并且整个字符串的二进制长度要最短，并且该二进制不能有歧义，如a是0，b是1，c是01，那么，01到底是ab还是c
    priority_queue<long long, vector<long long>, greater<long long>> q;//存字符出现次数，每次选择最小和次小的值，来构建哈夫曼树（最优二叉树）
    long long n = 0;
    cin >> n;

    if (n == 1)
    {
        long long x = 0;
        cin >> x;
        return x;
    }

    for (long long i = 0; i < n; ++i)
    {
        long long x = 0;
        cin >> x;
        q.push(x);
    }

    long long result = 0;
    while (q.size() > 1)//图片有解析
    {
        long long num1 = q.top();
        q.pop();

        long long num2 = q.top();
        q.pop();

        result += num1 + num2;
        q.push(num1 + num2);
    }

    cout << result << endl;
    return 0;
}


/*
给出一个有n种字符组成的字符串，其中第i种字符出现的次数为ai。
请你对该字符串应用哈夫曼编码，使得该字符串的长度尽可能短，求编码后的字符串的最短长度。
输入描述：
第一行输入一个整数n(1≤n≤2⋅10^5)，表示字符种数。
第二行输入
n个整数ai(1≤ai≤10^9)，表示每种字符的出现次数。
输出描述：
输出一行一个整数，表示编码后字符串的最短长度。

示例1
输入：
3
1 2 3
输出：
9
说明：
三种字符的哈夫曼编码分别为["00","01","1"]时，长度最短，最短长度为9。
*/

